\usepackage{listings}
\lstset{language=Java,
        basicstyle=\small}

\usepackage{graphicx}
\usepackage{hyperref}
\hypersetup{
  colorlinks=true,
  urlcolor=blue,
  linkcolor=black
}
\mode<article>{\usepackage{fullpage}}

\title{Lecture Four -- Array Lists}
\author{Matt Bone}
\date{\today}

\begin{document}

\mode<article>{\maketitle}
\tableofcontents
\mode<article>{\pagebreak}
\mode<presentation>{\frame{\titlepage}}
\mode<article>{\setlength{\parskip}{.25cm}}

\section{Data Structures and The Java Collections Framework}

\subsection{Introduction}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Collections Framework -- Introduction}}

  \begin{quote}
  A collection — sometimes called a container — is simply an object
  that groups multiple elements into a single unit...A collections
  framework is a unified architecture for representing and manipulating
  collections.
  \end{quote}

  --from \url{http://java.sun.com/docs/books/tutorial/collections/intro/index.html}

\end{frame}
The Java Collections Framework provides implementations of most of the
data structures that we will study this semester.  Collections
frameworks are not necessarily unique to Java.  For example, C++ has
the Standard Template Library.  Other languages likr Python or
Scheme have some data structures baked into the `syntax' and libraries
or modules that implement others.

\subsection{What are we trying to accomplish?}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{What are we trying to accomplish?}}

  \begin{itemize}
  \item Learn to use the various data structures
  \item Study the implementations of various data structures
  \item \textbf{Be able to choose the appropriate data structure for
      the circumstances}
  \end{itemize}
\end{frame}
Most programmers these days are not faced with the task of
implementing data structures from scratch unless they are working on
programming language implementations or unusual platforms.  Even then,
the programmer should consult the myriad literature available on the
topic.  Still, even though programmers should attempt to utilize the
data structures that are available on whatever platform they are
using, these abstractions are somewhat leaky.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Leaky Abstractions}}
  In order to choose the appropriate data structure for a particular
  situtation we need to know something about the data structure's internals.
\end{frame}

\section{ArrayList Overview}

\subsection{List Interface}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{List Interface}}
  We will look at several implementions of our first generic data
  structure, the
  \href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html}{List}
  interface.
\end{frame}
The Java Collections Framework utilizes interfaces quite heavily.  For
instance, there are several implementations of the list interface and
each has pros and cons.  Here we will look at the
\href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html}{ArrayList}
implementation.  In our next lecture we will look at the
\href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html}{LinkedList}
implementation.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Programming to Interfaces}}
  Because we may want to switch between List implementations in the future,
  by programming to the List Interface, we can make this change transparently.

  Like many good an interesting aspects of software engineering, this allows us
  \textbf{to delay decisions as long as possible}.
\end{frame}

\subsection{Array Lists -- Our First Data Structure}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Array Lists -- Our First Data Structure}}

  AKA Dynamic Arrays, 
  \href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html}{ArrayList}s
  are quite simply arrays that grow as needed.

  \begin{center}\includegraphics[height=6cm]{arraylist_diag}\newline\end{center}

\end{frame}
In a standard array, we specify the maximum size at instantiation (in
some languages like C, this is specified at compile time, this is not
the case in Java).

For example:
\begin{lstlisting}
  //regular array, size specified at instantiation
  String[] strArray = new String[100];
\end{lstlisting}


\subsection{Life without Generics}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{List Interface}}
  Before Java 1.5

  \begin{lstlisting}
  ArrayList a = new ArrayList();
  a.add(new BigInteger("42");
  a.add(new BigInteger("43");

  //WRONG (won't compile):
  BigInteger i = a.get(0);
  
  //RIGHT:
  BigInteger i1 = (BigInteger) a.get(0);
  \end{lstlisting}
\end{frame}


\subsection{Life with Generics}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Life with Generics}}
  \begin{lstlisting}
  ArrayList<BigInteger> a = new 
                            ArrayList<BigInteger>();
  a.add(new BigInteger("42");
  a.add(new BigInteger("43");

  //Not allowed:
  a.add("Hello");

  //Works great, no cast necessary:
  BigInteger i = a.get(0);  
  \end{lstlisting}
\end{frame}
Generics give us a way of being more specific about a particular
collections.  For instance, in the example above, we were saying that
we wanted a list and that the list could only contain instances of the
\verb'BigInteger' class. Before generics we could not acheive this
level of specificity with the collections framework 'right out of the
box'. 

\section{ArrayList Implementation}

\subsection{Source}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Source}}
  Of interest is the \verb'ensureCapacity' method:
  \begin{lstlisting}
    //Copyright 2004 Sun Microsystems, Inc. 
    //All rights reserved.
    public void ensureCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            elementData = (E[])new Object[newCapacity];
            System.arraycopy(oldData, 0, 
                             elementData, 0, size);
        }
    }
  \end{lstlisting}
\end{frame}   
The \verb'ensureCapacity' method is where the real work of the dynamic
list is done (though oftentimes you will not call this method
explicitly).  Since the dynamic list is implemented on top of a
regular array, this method checks to see if that array can hold the
specified number of elements.  If it can, things continue normally.
Otherwise a new, larger array (\verb'(oldCapacity * 3)/2 + 1') is
created and the elements from the old array are copied over.  Though
we will examine what is actually happening here from a mathematical
standpoint later in the course, we can understand intuitively that
this must be an expensive operation in terms of time.


\subsection{Finding an Element}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Finding an Element}}
  \begin{lstlisting}
    public int indexOf(Object elem) {
        if (elem == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (elem.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
  \end{lstlisting}
\end{frame}        
Notice if we pass in a null, we return the first index that is a null
pointer.  Also, pay special attention to the code in the else block.
Here, we loop over the array and return the index of the first item
that \verb'.equals()' the passed in item. I told you
the \verb'.equals()' was important!


\subsection{Removal}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Removal}}
  \begin{lstlisting}
  public E remove(int index) {
        RangeCheck(index);

        modCount++;
        E oldValue = elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, 
                             elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
    } 
  \end{lstlisting}
\end{frame}        
Notice that if we remove an item in the middle of the list, the list
is `collapsed' or re-copied so that everything is again contiguous.

\end{document}

